#pragma once

#include<iostream>
#include<string>
using namespace std;


template<class K>
struct TreeNode {
public:	
	TreeNode(const K& key =0) :_key(key),_left(nullptr), _right(nullptr)
	{

	}


public:
	K _key;
	TreeNode<K>* _left;
	TreeNode<K>* _right;
};

template<class K>
class BSTree {
	typedef TreeNode<K> Node;
public:
	BSTree() 
		:_node(nullptr)
	{
	}

	bool Insert(const K& key) {
		if (!_node) {
			_node = new Node(key);
			return true;
		}
		//递归去找空的结点
		Node* parent = nullptr;
		Node* cur = _node;
		while (cur) {
			//保存以下父节点
			parent = cur;
			if (cur->_key < key)
				cur = cur->_right;
			else if (cur->_key > key)
				cur = cur->_left;
			else 
				return false;
		}
		//插入结点
		cur = new Node(key);
		if (parent->_key < key)
			parent->_right = cur;
		else
			parent->_left = cur;
		return true;
	}

	void InOrder() {
		_InOrder(_node);
	}

	bool Find(const K& key) {
		Node* cur = _node;
		while (cur) {
			if (cur->_key < key)
				cur = cur->_right;
			else if (cur->_key > key)
				cur = cur->_left;
			else
				return true;
		}
		return false;
	}

	bool Erase(const K& key) {
		Node* cur = _node;
		Node* parent = nullptr;
		while (cur) {
			if (cur->_key < key) {
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_key > key) {
				parent = cur;
				cur = cur->_left;
			}
			else {
				//找到了
				//第一种情况，cur->letf为空
				if (!cur->_left) {
					if (cur == _node)
						_node = cur->_right;
					
					//判断连在父亲的左还是右边
					else if (parent->_right==cur)
						parent->_right = cur->_right;
					else
						parent->_left = cur->_right;
					delete cur;
				}
				//第二种情况，cur->right为空
				else if (!cur->_right) {
					if (cur == _node)
						_node = cur->_left;
					else if (parent->_left == cur)
						parent->_left = cur->_left;
					else
						parent->_right = cur->_left;
					delete cur;
				}
				//左右都不为空
				else {
					//思路，交换后删除
					//交换的点，左子树的最大，右子树的最小
					Node* parent = cur;
					Node* subLeft = cur->_right;
					while (subLeft->_left) {
						parent = subLeft;
						subLeft = subLeft->_left;
					}
					//可以交换结点了
					swap(subLeft->_key, cur->_key);
					if (subLeft == parent->_left)
						parent->_left = subLeft->_right;
					else 
						parent->_right = subLeft->_right;
					delete subLeft;
				}
				return true;
			}
			
		}
	}

	bool FindR(const K& key) {
		return _FindR(_node,key);
	}

	bool InsertR(const K& key) {
		return _InsertR(_node, key);
	}

	bool EraseR(const K& key) {
		return _EraseR(_node, key);
	}
private:
	bool _EraseR(Node*& node, const K& key) {
		if (!node) {
			return false;
		}
		if (node->_key < key)
			return _EraseR(node->_right, key);
		else if (node->_key > key)
			return _EraseR(node->_left, key);
		else {
			//判断左右为空
			if (!node->_left) {
				Node* del = node;
				node = node->_right;
				delete del;
				return true;
			}
			else if (!node->_right) {
				Node* del = node;
				node = node->_left;
				delete del;
				return true;
			}
			else {
				//左右孩子都不为空
				//找由孩子的最左
				Node* subLeft = node->_right;
				while (subLeft->_left) {
					subLeft = subLeft->_left;
				}
				//交换俩数
				swap(subLeft->_key, node->_key);
				//递归删除
				return _EraseR(node->_right, key);
			}
		}
	}


	void _InOrder(Node* node) {
		if (!node)
			return;
		_InOrder(node->_left);
		cout << node->_key << "->";
		_InOrder(node->_right);
	}

	bool _InsertR(Node*& node, const K& key) {
		if (!node) {
			//可以插入了
			node = new Node(key);
			return true;
		}
		
		if (node->_key < key)
			return _InsertR(node->_right,key);
		else if (node->_key > key)
			return _InsertR(node->_left, key);

		else
			return false;
	}
	bool _FindR(Node* node,const K& key) {
		if (!_node)
			return false;
		if (node->_key < key)
			return _FindR(node->_right,key);
		else if (node->_key > key)
			return _FindR(node->_left,key);
		else
			return true;
	}

private:
	TreeNode<K>* _node;
};